package com.zjsru.oneDay;

import java.util.*;

/**
 * 到达目的地的第二短时间
 *
 *
 * 输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
 * 输出：13
 * 解释：
 * 上面的左图展现了给出的城市交通图。
 * 右图中的蓝色路径是最短时间路径。
 * 花费的时间是：
 * - 从节点 1 开始，总花费时间=0
 * - 1 -> 4：3 分钟，总花费时间=3
 * - 4 -> 5：3 分钟，总花费时间=6
 * 因此需要的最小时间是 6 分钟。
 *
 * 右图中的红色路径是第二短时间路径。
 * - 从节点 1 开始，总花费时间=0
 * - 1 -> 3：3 分钟，总花费时间=3
 * - 3 -> 4：3 分钟，总花费时间=6
 * - 在节点 4 等待 4 分钟，总花费时间=10
 * - 4 -> 5：3 分钟，总花费时间=13
 * 因此第二短时间是 13 分钟。
 *
 */

public class secondMinimum {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<Integer>[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int[] edge: edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        // path[i][0] 表示从 1 到 i 的最短路长度，path[i][1] 表示从 1 到 i 的严格次短路长度
        int[][] path = new int[n + 1][2];
        for(int i = 0;i <= n; i++){
            Arrays.fill(path[i],Integer.MAX_VALUE);
        }
        path[1][0] = 0;
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{1,0});
        while(path[n][1] == Integer.MAX_VALUE){
            int[] arr = queue.poll();
            int cur = arr[0],len =arr[1];
            for (int next:graph[cur]) {
                if(len + 1< path[next][0]){
                  path[next][0] = len + 1;
                  queue.offer(new int[]{next,len + 1});
                }else if(len + 1 > path[next][0] && len + 1< path[next][1]){
                    path[next][1] = len + 1;
                    queue.offer(new int[]{next,len + 1});
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < path[n][1]; i++) {
            if(ret % (2 * change) >= change){
                ret = ret + (2 * change - ret % (2 * change));
            }
            ret = ret + time;
        }
        return ret;
    }
    public static void main(String[] args){
       secondMinimum secondMinimum = new secondMinimum();
        int n = 5;
        int[][] edges = new int[][]{{1,2},{1,3},{1,4},{3,4},{4,5}};
        int time = 3;
        int change = 5;
        System.out.println(secondMinimum.secondMinimum(n,edges,time,change));
    }
}
